﻿#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;

//力扣源码:https://leetcode.cn/problems/duplicate-zeros/
//复写零

/*
1. 双指针模拟插入逻辑
cur指针：从前往后遍历原数组，标记当前读取位置。

dest指针：动态计算插入后的理论目标位置，标记最终数组的写入位置。

模拟插入过程：通过一次正向遍历，计算dest和cur的最终停止位置，避免覆盖未处理的元素。

2. 两阶段处理
阶段一：计算边界
正向遍历：根据当前元素是否为0，决定dest移动步长（0则移动2步，否则1步）。

// 示例：
// 原数组: [1,0,2,3,0,4,5,0]
// 阶段一结束时：
//   cur=5 (指向元素4)，dest=7 (目标位置)


阶段二：逆向填充
    从后向前处理：避免覆盖未处理的原始数据。
    分类处理：
        若当前元素是0：
            在dest和dest-1位置写入0（复制一个0）。
            dest回退2步。

        若当前元素非0：
            直接复制到dest位置，dest回退1步。
*/



int main() {
    // 原始数组，需要就地复制0元素（每个0后面插入一个0，后续元素后移，超出部分截断）
    vector<int> nums({ 1, 0, 2, 3, 0, 4, 5, 0 });
    int dest = -1; // 目标位置指针，表示最终数组的当前写入位置
    int cur = 0;   // 当前读取位置的指针

    // 第一阶段：计算目标位置和当前指针的最终位置
    // 通过模拟插入操作，找到原数组中需要保留的元素范围
    while (1) {
        if (nums[cur] == 0) {
            dest += 2; // 遇到0，dest需要移动两格（因为插入一个0）
            if (dest >= (int)nums.size() - 1)
                break; // 如果目标位置超出数组边界，停止计算
            cur++;
        }
        else {
            dest++;    // 非0元素，dest移动一格
            if (dest >= (int)nums.size() - 1)
                break; // 同上，超出边界则停止
            cur++;
        }
    }
    // 循环结束后，cur指向最后一个需要处理的原数组元素位置
    // dest指向理论上的目标位置（可能需要调整）

    // 第二阶段：从后向前填充数组，避免覆盖未处理的元素
    while (cur >= 0) {
        // 处理dest越界的情况（当最后一个元素是0时，可能没有足够空间插入两个0）
        if (dest >= nums.size()) {
            nums[dest - 1] = 0; // 只能在倒数第二格插入一个0
            dest -= 2;           // 移动dest指针到前两格
            cur--;               // 已处理当前元素，向前移动cur
            continue;
        }

        // 根据当前元素是否为0进行不同处理
        if (nums[cur] == 0) {
            // 插入两个0
            nums[dest] = 0;      // 目标位置写0
            nums[dest - 1] = 0;  // 前一格也写0（相当于复制）
            dest -= 2;           // 移动两格准备写入下一个元素
            cur--;               // 处理前一个元素
        }
        else {
            // 非0元素直接复制
            nums[dest--] = nums[cur--]; // 复制并移动指针
        }
    }

    // 输出结果
    for (auto& e : nums) {
        cout << e << " ";
    }
    return 0;
}